package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/10 10:23
 **/
public class Day8_3_Num221_MaximalSquare {
    class Solution {
        // 最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。
        int max = 0;
        public int maximalSquare(char[][] matrix) {
            if(matrix.length == 0 || matrix[0].length == 0) return 0;
            int m = matrix.length, n = matrix[0].length;
            int[][] dp = new int[m+1][n+1];
            for(int i = 1; i <= m; ++i){
                for(int j = 1; j <= n; ++j){
                    if(matrix[i-1][j-1] == '1'){
                        dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
                        max = Math.max(max, dp[i][j]);
                    }
                }
            }
            return max * max;
        }
    }
}